package main;

import java.lang.Comparable;
import java.util.NoSuchElementException;

public class BST
{
	private static class Node<E>
	{
		private Node<E> left;
		private Node<E> right;
		private Comparable<E> data;
				
		private Node(Comparable<E> data)
		{
			this.left = null;
			this.right = null;
			this.data = data;
		}
	}
	
	private Node<?> root; 
	private int count; 
	
	public int getCount() 
	{
		return count;
	}

	public void setCount(int count) 
	{
		this.count = count;
	}

	public BST()
	{
		root = null;
		count = 0;
	}
	
	public Node<?> findMax(Node<?> currentNode)
	{
		if (currentNode.right == null)
			return currentNode;
		else
			 return findMax(currentNode.right);
	}
	
	
	public boolean contains(Comparable<?> dataToFind)
	{
		return hasData(root, dataToFind);
	}
	
	private boolean hasData(Node<?> current, Comparable dataToFind)
	{
		if (current == null)
			return false;
		int result = dataToFind.compareTo(current.data);
		if (result == 0)
			return true;
		else if (result < 0)
			return hasData(current.left, dataToFind);
		else
			return hasData(current.right, dataToFind);
	}
	
	public void print()
	{
		
	}
	
	public void insert(Comparable<?> data)
	{
		root = add(root, data);
	}
	
	private Node add(Node current, Comparable dataToAdd)
	{
		if (current == null)
		{
			count++;
			current = new Node(dataToAdd);
			return current;
		}
		else
		{
			int result = dataToAdd.compareTo(current.data);
			if (result < 0)
			{
				current.left = add(current.left, dataToAdd);
				return current;
			}
			else
			{
				current.right = add(current.right, dataToAdd);
				return current;
			}
		}
	}

	public void delete (Comparable data) throws NoSuchElementException
	{
		root = remove(root, data);
	}
	
	private Node remove (Node current, Comparable dataToRemove)
	{
		if (current == null)
			throw new NoSuchElementException();
		else
		{
			int result = dataToRemove.compareTo(current.data);
			if (result < 0)
			{
				current.left = remove (current.left, dataToRemove);
				return current;
			}
			else if (result > 0)
			{
				current.right = remove (current.right, dataToRemove);
				return current;
			}
			else
			{
				if (current.left == null && current.right == null)
				{
					System.out.println("i'm here");
					count--;
					current = null;
					return current;
				}
				else if (current.left == null && current.right != null)
				{
					count--;
					current = current.right;
					return current;
				}
				else if (current.left != null && current.right == null)
				{
					count--;
					current = current.left;
					return current;
				}
				else
				{
					
					Node inOrderPredecessor = findMax(current.left);
					current.data = inOrderPredecessor.data;
					
					if (inOrderPredecessor.left != null)
					{
						inOrderPredecessor = inOrderPredecessor.left;
						inOrderPredecessor.left = null;
					}
					else if (inOrderPredecessor.right != null)
					{
						inOrderPredecessor = inOrderPredecessor.right;
						inOrderPredecessor.right = null;
					}					
					count--;
					return current;
				}
			}
		}
	}
}
